Maszyny wektorów nośnych (Support Vector Machines)

Maszyny wektorów nośnych (z ang. Support Vector Machines, w skrócie SVM) to rodzina metod uczenia maszynowego służących do klasyfikacji oraz regresji. Algorytmy SVM opierają się na koncepcji maksymalizacji marginesu (ang. margin) pomiędzy punktami danych różnych klas, przy jednoczesnym dopuszczeniu pewnych błędów w przypadku miękkiego marginesu.

Historia

Podstawy teoretyczne SVM wywodzą się z badań nad geometrią analityczną i statystyką w latach 60. XX wieku. Pierwsze pełne przedstawienie algorytmu pojawiło się w pracach Vapnika i Czerwonienkisa pod nazwą optimal hyperplane. W 1995 roku Corinna Cortes i Vapnik opublikowali przełomowy artykuł, w którym wprowadzono koncepcję kernel trick, umożliwiającą efektywne działanie SVM w przestrzeniach o dużej wymiarowości.

Podstawowa teoria

W najprostszym wariancie, zwanym hard margin SVM, szukamy hiperpowierzchni (hiperpłaszczyzny) w przestrzeni Hilberta, która maksymalizuje odległość (margines) od najbliższych punktów treningowych – tzw. wektorów nośnych (support vectors). Formalnie, dla zbioru uczącego {(x_i, y_i)}_{i=1}^N, gdzie x_i∈ℝ^d i y_i∈{−1,1}, rozwiązujemy problem:

min⁡ ½‖w‖²
przy warunkach: y_i (w·x_i + b) ≥ 1,   i = 1,…,N

Rozwiązaniem jest para (w, b), która definiuje decyzję klasyfikacyjną f(x) = sign(w·x + b).

Miękki margines i funkcja kary

W praktyce dane często nie są separowalne liniowo. Wprowadzono wtedy soft margin SVM, w którym dopuszcza się naruszenia marginesu poprzez zmienne kary ξ_i i parametr regularyzacji C:

min⁡ ½‖w‖² + C Σ_i ξ_i
przy warunkach: y_i (w·x_i + b) ≥ 1 − ξ_i,   ξ_i ≥ 0

Wartość C kontroluje kompromis między maksymalizacją marginesu a dopuszczalnym błędem klasyfikacji.

Kernel trick

W celu radzenia sobie z nieliniowo separowalnymi danymi wprowadzono funkcję jądra K(x, x′), która oblicza iloczyn skalarny w wyższej wymiarowości bez jej wyraźnego wyznaczania. Najpopularniejsze jądra to:

• jądro liniowe – K(x, x′)=x·x′
• jądro wielomianowe – K(x, x′) = (γ x·x′ + r)^d
• jądro radialne (RBF) – K(x, x′) = exp(−γ‖x−x′‖²)
• jądro sigmoidalne – K(x, x′) = tanh(γ x·x′ + r)

Dzięki kernel trick SVM może tworzyć nieliniowe granice decyzyjne w oryginalnej przestrzeni.

Zastosowania

Maszyny wektorów nośnych znalazły zastosowanie w wielu dziedzinach, m.in.:

• Rozpoznawanie pisma ręcznego (MNIST)
• Biomedycyna – klasyfikacja genów i diagnozowanie chorób
• Systemy rozpoznawania mowy i dźwięku
• Analiza tekstu i klasyfikacja dokumentów (NLP)
• Detekcja anomalii w systemach przemysłowych

Zalety i wady

Zalety

• Stabilność i dobra generalizacja przy małych i średnich zbiorach danych.
• Możliwość zastosowania dowolnej funkcji jądra.
• Jednoznaczny optimalny rozwiązanie (problem wypukły).

Wady

• Wysoki koszt obliczeniowy przy bardzo dużych zbiorach (zależny od liczby wektorów nośnych).
• Wrażliwość na dobór parametrów C i wyboru jądra.
• Trudności w interpretacji modelu przy złożonych jądrach.

Algorytmy optymalizacji

W praktyce rozwiązanie problemu SVM uzyskuje się najczęściej metodami:

• metodą gradientu prostego (SGD) – szczególnie przy dużych danych.
• Sequential Minimal Optimization (SMO) – efektywna metoda rozwiązywania problemu dualnego.
• Algorytmy wewnętrznego punktu (interior‑point).

Implementacje i biblioteki

Popularne otwarto‑źródłowe biblioteki umożliwiające wykorzystanie SVM w praktyce to m.in.:

• scikit‑learn (Python)
• LIBSVM
• mlpack
• TensorFlow – wsparcie dla SVM jako warstwy w modelach głębokich.

Powiązane pojęcia

Więcej informacji można znaleźć w artykułach: Uczenie automatyczne, Statystyka, Klasyfikacja, Regresja, Redukcja wymiarowości.

Bibliografia

1. Vapnik, V. (1995). The Nature of Statistical Learning Theory. Springer.
2. Cortes, C., & Vapnik, V. (1995). Support‑vector networks. Machine Learning, 20(3), 273–297.
3. Schölkopf, B., & Smola, A. J. (2002). Learning with Kernels. MIT Press.